package 代码随想录_动态规划;

import java.util.ArrayList;
import java.util.List;

/**
  dp数组开 n 个还是开 n+1 个,要看第n个位置会不会用到,要是用到,开n+1个

  01_背包：外层遍历物品,内层背包,内层倒序遍历,保证每个物品只取一次

  完全背包：
          求组合数就是外层for循环遍历物品,内层for遍历背包
          求排列数就是外层for遍历背包,内层for循环遍历物品,且内循环正序
          顺序不同的序列被视作不同的组合(就是排列),反之,才是真正的组合

  另外：求组合数的dp方程一般都这样：dp[j] += dp[j - coins[i]](待验证)

          在求最小...(个数、方案)类题时,322、279并且递推公式有限制条件
          考虑递推公式的特性,dp[j]必须初始化为一个最大的数
          否则就会在min(....., dp[j])比较的过程中被初始值覆盖;非0元素都应该是最大值。
          一般限制条件：dp[...] != Integer.MAX_VALUE

  打家劫舍II和I的越界问题还是很细节的

  子序列题型：连续不连续,公共不公共,再加上一个特殊的53子序和

  编辑距离系列：初始化和递归公式每个题有细微差距,其它都差不多

  回文：647-求数量  516-求最长长度(有初始化了)   5-求最长长度
  回文子串和最长回文子串掌握中心拓展法,动态规划怪怪的

 *
 */
public class Test1 {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE, max = 1, min = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = max;
                max = min;
                min = temp;
            }
            max = Math.max(max * nums[i], nums[i]);
            min = Math.min(min * nums[i], nums[i]);

            res = Math.max(res, max);
        }
        return res;
    }
}

